package solution;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;
import javafx.scene.shape.ArcTo;
import javafx.scene.shape.LineTo;
import jdk.internal.dynalink.linker.LinkerServices;
import jdk.nashorn.internal.runtime.ListAdapter;
import sun.reflect.generics.tree.Tree;

import javax.management.QueryEval;
import java.util.*;
import java.util.function.BinaryOperator;

public class Main {
    static class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode() {
        }
    }

    public static TreeNode root;

    public static int i = 0;

    public TreeNode creatTree (String string, TreeNode node) {
        if (string == null) return null;
        if (i < string.length() && string.charAt(i) != '#') {
            TreeNode tmpNode = new TreeNode(string.charAt(i++));
            node = tmpNode;
            node.left = creatTree(string, node.left);
            node.right = creatTree(string, node.right);
        } else {
            i++;
        }
        return node;
    }

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Main m = new Main();
        while (scanner.hasNextLine()) {
            String string = scanner.nextLine();
            root = new TreeNode();
            root = m.creatTree(string, root);
            m.inOrder(root);
        }
    }

    public void inOrder (TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public int depth;
    public int maxDepth (TreeNode root) {
        if (root == null)
            return 0;
        else {
            int leftD = maxDepth(root.left);
            int rightD = maxDepth(root.right);
            return leftD > rightD ? leftD + 1 : rightD + 1;
        }
    }

    public boolean isBalanced (TreeNode root) {
        if (root == null)
            return true;
        int leftD = maxDepth(root.left);
        int rightD = maxDepth(root.right);
        if (Math.abs(leftD - rightD) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }

    public boolean isSameTree (TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 != null || root1 != null && root2 == null) {
            return false;
        } else if (root1 == null && root2 == null) {
            return true;
        } else if (root1.val == root2.val) {
            return isSameTree(root1.left, root2.left) && isSameTree(root2.right, root1.right);
        }
        else {
            return false;
        }
    }


    public boolean isSubtree (TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        } else if (root == null && subRoot != null) {
            return false;
        } else{
            return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        }
    }

    public static void main2(String[] args) {
        TreeNode r1 = new TreeNode('c');
        TreeNode r2 = new TreeNode('c');
        TreeNode r3 = new TreeNode('c');
        r1.left = r2;
        Main m = new Main();
        boolean b = m.isSubtree(r1, r3);
        System.out.println(b);
    }

    public boolean isSameNode (TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        } else if (l == null || r == null) {
            return false;
        }
        if (l.val == r.val) {
            return isSameNode(l.left, r.right) && isSameNode(l.right, r.left);
        } else {
            return false;
        }
    }

    public boolean isSymmetric (TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSameNode(root.left, root.right);
    }

    public TreeNode invertTree (TreeNode root) {
        if (root == null) {
            return null;
        }
        else {
            TreeNode tmpNode = root.left;
            root.left = root.right;
            root.right = tmpNode;
            invertTree(root.right);
            invertTree(root.left);
        }
        return root;
    }


    TreeNode preNode = null;

    public TreeNode creat () {
        TreeNode t10 = new TreeNode(10);
        TreeNode t6 = new TreeNode(6);
        TreeNode t4 = new TreeNode(4);
        TreeNode t8 = new TreeNode(8);
        TreeNode t12 = new TreeNode(12);
        TreeNode t14 = new TreeNode(14);
        TreeNode t16 = new TreeNode(16);
        t10.left = t6;
        t10.right = t14;
        t6.left = t4;
        t6.right = t8;
        t14.left = t12;
        t14.right = t16;
        return t10;
    }

    public static void main4(String[] args) {
        Main m = new Main();
        TreeNode pTreeRoot = m.creat();
        TreeNode ret = m.Convert(pTreeRoot);
        while (ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.right;
        }
//        System.out.println();
//        TreeNode pTreeRoot2 = m.creat();
//        ret = m.Convert2(pTreeRoot2);
//        while (ret != null) {
//            System.out.print(ret.val + " ");
//            ret = ret.left;
//        }
    }

    public TreeNode Convert2 (TreeNode root) {
        TreeNode tmpNode2 = convert(root);
        while (tmpNode2.right !=  null) {
            tmpNode2 = tmpNode2.right;
        }
        return tmpNode2;
    }

    public TreeNode Convert (TreeNode root) {
        if(root == null) return null;
        TreeNode tmpNode = convert(root);
        while (tmpNode.left != null) {
            tmpNode = tmpNode.left;
        }
        return tmpNode;
    }

    public TreeNode convert (TreeNode root) {
        if (root == null)
            return null;
        convert(root.left);
        root.left = preNode;
        if (preNode != null) {
            preNode.right = root;
        }
        preNode = root;
        root.right = convert(root.right);
        return root;
    }


    public int curIndex = 0;

//    public int findIndex (int[] inorder, int key, int inBegin, int inEnd) {
//        int i = inBegin;
//        while (i < inEnd) {
//            if (key == inorder[i])
//                return i;
//        }
//        return -1;
//    }
//
//    public int preOrderIndex = 0;
//
//    public TreeNode buildTreeChild (int[] preorder, int[] inorder, int inBegin, int inEnd) {
//        if (inBegin > inEnd) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[preOrderIndex]);
//        int i = findIndex(inorder,preorder[preOrderIndex++], inBegin, inEnd);
//        root.left = buildTreeChild(preorder, inorder, inBegin, i-1);
//        root.right = buildTreeChild(preorder, inorder, i+1, inEnd);
//        return root;
//    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildTreeChild(preorder, inorder, 0, inorder.length-1);
//    }

    /**
     * 意义是找到当前结点的index，好得到子树的inBegin和inEnd
     * @param inorder 中序遍历的数组
     * @param key 目标值（当前根节点的值）
     * @param inBegin 中序遍历的开始
     * @param inEnd 中序遍历的结束
     * @return
     */
    public int findRoot (int[] inorder, int key, int inBegin, int inEnd) {
        for (int j = inBegin; j <= inEnd; j++) {
            if (key == inorder[j]) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 目的是得到子树都构建好的结点，返回给上层
     * @param inorder
     * @param postorder
     * @param inBegin
     * @param inEnd
     * @return 得到左右子树都构建好的结点
     */
    public TreeNode buildChild (int[] inorder, int[] postorder, int inBegin, int inEnd) {
        if (inBegin > inEnd) {
            return null;
        }
        //用后序的postIndex下标构建root
        TreeNode root = new TreeNode(postorder[postIndex--]);
        //得到root所在的下标
        int rootIndex = findRoot(inorder, root.val, inBegin, inEnd);
        root.right = buildChild(inorder, postorder, rootIndex + 1, inEnd);
        root.left = buildChild(inorder, postorder, inBegin, rootIndex - 1);
        return root;
    }

    public int postIndex = 0;

    public TreeNode buildTree (int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        TreeNode root = buildChild(inorder, postorder, 0, postIndex);
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public StringBuilder tree2strChild (TreeNode root, StringBuilder stringBuilder) {
        if (root.left != null) {
            stringBuilder.append('(');
            stringBuilder.append(root.left.val);
            stringBuilder = tree2strChild(root.left, stringBuilder);
            stringBuilder.append(')');
            if (root.right == null) {
                return stringBuilder;
            } else {
                stringBuilder.append('(');
                stringBuilder.append(root.right.val);
                stringBuilder = tree2strChild(root.right, stringBuilder);
                stringBuilder.append(')');
                return stringBuilder;
            }
        } else {
            if (root.right != null) {
                stringBuilder.append("()(");
                stringBuilder.append(root.right.val);
                stringBuilder = tree2strChild(root.right, stringBuilder);
                stringBuilder.append(')');
                return stringBuilder;
            } else {
                return stringBuilder;
            }
        }
    }

    public String tree2str (TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(root.val);
        stringBuilder = tree2strChild(root, stringBuilder);
        return stringBuilder.toString();
    }


    public List<Integer> preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        } else {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curNode = root;
            while (curNode != null || !stack.empty()) {
                while (curNode != null) {
                    stack.push(curNode);
                    list.add(curNode.val);
                    curNode = curNode.left;
                } //curNode == null后，栈顶存储的是前一个的root结点
                TreeNode top = stack.pop();
                curNode = top.right;
            }
        }
        return list;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == q || root == p) {
            return root;
        }
        TreeNode leftT = lowestCommonAncestor(root.left, p, q);
        TreeNode rightT = lowestCommonAncestor(root.right, p, q);
        if (leftT != null && rightT != null) {
            return root;
        } else if (leftT != null) {
            return leftT;
        } else {
            return rightT;
        }
    }

    public List<Integer> inorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            list.add(curNode.val);
            curNode = curNode.right;
        }
        return list;
    }

    public List<Integer> postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        TreeNode prev = null;

        //!stack.empty()表示还有根结点没有存到list当中
        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                prev = top;
            } else {
                curNode = top.right;
            }
        }
        return list;
    }

    public List<List<Integer>> levelOrder (TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        /**
         * 因为每次都会判断结点是否有子结点，有就会加到队列里头
         * 所以队列为空就代表遍历到头了
         */
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int levelLength = queue.size();
            /**
             * 虽然每次循环都可能添加结点到队列中
             * 但是因为levelLength没有被重新赋值，所以不影响层序遍历的功能
             */
            while (levelLength != 0) {
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                levelLength--;
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }

    public List<List<Integer>> levelOrderBottom (TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        /**
         * 因为每次都会判断结点是否有子结点，有就会加到队列里头
         * 所以队列为空就代表遍历到头了
         */
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int levelLength = queue.size();
            /**
             * 虽然每次循环都可能添加结点到队列中
             * 但是因为levelLength没有被重新赋值，所以不影响层序遍历的功能
             */
            while (levelLength != 0) {
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                levelLength--;
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            ret.add(list);
        }
        /**
         * 通过栈的先进后出将顺序表逆序
         */
        Stack<List<Integer>> stack = new Stack<>();
        while (ret.size() !=  0) {
            stack.push(ret.remove(0));
        }
        while (!stack.empty()) {
            ret.add(stack.pop());
        }
        return ret;
    }

}
